package site.wanjiahao.sort.uncompare;

import site.wanjiahao.sort.Sort;

import java.util.Arrays;

// 排序算法使用插入排序
public class RadixSort1 extends Sort<Integer> {


    @Override
    protected void sort() {
        // 先对各位，十位，百位，后续进行计数排序，因为计数排序比较适合一定范围内排序
        int max = array[0];
        for (int e: array) {
            if (e > max) {
                max = e;
            }
        }
        int[] counts = new int[10];
        int[] output = new int[array.length];
        for (int divider = 1; divider <= max; divider *= 10) {
            countingSort(divider, counts, output);
        }
    }
    
    private void countingSort(int divider, int[] counts, int[] output) {
        Arrays.fill(counts, 0);
        // 存入计数
        for (int e: array) {
            counts[e / divider % 10]++;
        }
        for (int i = 1; i < counts.length; i++) {
            counts[i] += counts[i - 1];
        }
        // 遍历数组元素
        for (int i = array.length - 1; i >= 0 ; i--) {
            int cur = array[i];
            output[--counts[cur / divider % 10]] = cur;

        }

        for (int i = 0; i < array.length; i++) {
            array[i] = output[i];
        }
    }
}
